package implementacion;

import TDA.MatrizTDA;

public class Sudoku {
	
	public static boolean sudokuValido(int digitos, MatrizTDA<Integer> tablero ){
		boolean respuesta = true;
		for (int fila=0; fila<tablero.obtenerDimension();fila++){
			for(int columna=0;columna<tablero.obtenerDimension();columna++){
				//COMPRUEBA QUE NO SE REPITA EL VALOR EN LA FILA
				if(existeFila(fila, columna, tablero)==true){
					respuesta=false;
				}
				//COMPRUEBA QUE NO SE REPITA EL VALOR EN LA COLUMNA.
				if(existeColumna(fila, columna, tablero)==true){
					respuesta=false;
				}
				//COMPRUEBA QUE EL VALOR NO ESTA EN LA CAJA.
				if(existeCuadrante(fila, columna, tablero)==true){
					respuesta=false;
				}
			}
		}	
		/*if (respuesta == false)
			System.out.println ("El sudoku no es valido");
		else
			System.out.println("El sudoku es valido");
		*/
		return respuesta;
	}
	
	//METODO PARA COMPROBAR FILAS.
	private static boolean existeFila(int fila, int columna, MatrizTDA<Integer> tablero) {
		int valor = tablero.obtenerValor(fila, columna);
		boolean resultado = false;
		if (valor!=0){
			for (int columnaAux=0; columnaAux<tablero.obtenerDimension();columnaAux++){
				if(tablero.obtenerValor(fila, columnaAux)==valor && columna!=columnaAux){
					resultado=true;
				}
			}
		}
		return resultado;
	}
	
	//METODO PARA COMPROBAR COLUMNAS
		private static boolean existeColumna(int fila, int columna, MatrizTDA<Integer> tablero) {
			int valor = tablero.obtenerValor(fila, columna);
			boolean resultado = false;
			if(valor!=0){
				for (int filaAux=0; filaAux<tablero.obtenerDimension();filaAux++){
					if(tablero.obtenerValor(filaAux, columna)==valor && fila!=filaAux){
						resultado=true;
					}
				}
			}
			return resultado;
		}
	
	//METODO PARA COMPROBAR CUADRANTES
	public static boolean existeCuadrante (int fila, int columna, MatrizTDA<Integer> tablero){
	 	int minimo_fila;
		int maximo_fila;
		int minimo_columna;
		int maximo_columna;
		int contadorCuadrante = 0;
		int valor = tablero.obtenerValor(fila, columna);
		boolean resultado = false;
		//DETERMINAMOS LAS FILAS DE LA CAJA.
		if (fila>=0 && fila<3){
			minimo_fila = 0;
			maximo_fila = 2;
		}	else if (fila>2 &&fila<6 ){
			minimo_fila = 3;
			maximo_fila = 5;
		}else{
			minimo_fila = 6;
			maximo_fila = 8;
		}  
		//DETERMINAMOS LAS COLUMNAS DE LA CAJA.
		if (columna>=0 && columna < 3){
			minimo_columna = 0;
			maximo_columna = 2;
		}else if (columna>2 && columna<6){
			minimo_columna = 3;
			maximo_columna = 5;
		}else{
			minimo_columna = 6;
			maximo_columna = 8;
		}
		//RECORREMOS EL RANGO DE LA CAJA, Y BUSCAMOS EL VALOR.
		if(valor!=0){
			for (int f=minimo_fila; f<=maximo_fila; f++){
				for (int c=minimo_columna; c<=maximo_columna; c++){
					if (tablero.obtenerValor(f, c)==valor){
						contadorCuadrante++;
						
					}
					
				}
			}
		}
		if (contadorCuadrante > 1)
			resultado = true;
	   	return resultado;
	}
	
	//METODO QUE IMPRIME LA MATRIZ.
	public static void mostrarTablero (MatrizTDA<Integer> tablero){
		System.out.println( " |----------------------------| " );
		for (int fila=0; fila < tablero.obtenerDimension(); fila++ ){
			System.out.print(" | ");
		 
			for (int columna=0; columna < tablero.obtenerDimension(); columna++){
				if (tablero.obtenerValor(fila, columna) != 0)
					System.out.print (tablero.obtenerValor(fila, columna));
				else
					System.out.print ("0");
				if (columna==2 || columna==5)
					System.out.print ("|| ");
				else
					System.out.print ("| ") ;
			}
		
			System.out.println();
			if (fila!=2 && fila!=5)
				System.out.print( " |----------------------------| " );
			else
				System.out.print( " |============================| " );
			System.out.println();
		}
	}
	
	
	public static MatrizTDA<Integer> ResolverSudokuBK(int digitos, MatrizTDA<Integer> tablero, Posicion posActual, int numerosUbicados){
		Resolver(digitos,tablero, posActual);
		return tablero;
		}
	
	public static boolean Resolver(int digitos, MatrizTDA<Integer> tablero, Posicion pos)
		{
			if(pos == null || pos.x>tablero.obtenerDimension() || pos.y>tablero.obtenerDimension())
			{				
				return true;
			}
			if(tablero.obtenerValor(pos.x, pos.y) != 0)
			{
				return Resolver(digitos, tablero, proximaPosicion(tablero, pos));
				
			}	
			for (int i = 1; i<=digitos;i++)
			{
				tablero.setearValor(pos.x, pos.y, i);
				boolean valid = sudokuValido(tablero.obtenerDimension(), tablero);
				if(!valid)
				{
					tablero.setearValor(pos.x, pos.y, 0);
					continue;
				}
				boolean resuelto = Resolver(digitos, tablero, proximaPosicion(tablero, pos));
				if(resuelto)
				{
					return true;
				} else {
					tablero.setearValor(pos.x, pos.y, 0);
				}
			}
		return false;
		}
		
	
	public static Posicion proximaPosicion(MatrizTDA<Integer> tablero, Posicion pos) {
		Posicion aux = new Posicion();
		int x = pos.x;
		int y = pos.y;
		y = y+1;
		if(y>=tablero.obtenerDimension())
		{
			y = 0;
			x = x + 1;
		}
		
		if(x>=tablero.obtenerDimension())
			return null;
		aux.y = y;
		aux.x = x;
		return aux;
	}
	
	public static MatrizTDA<Integer> ResolverSudokuBKConPoda(MatrizTDA<Integer> tablero, Posicion posActual, int numerosUbicados, MatrizTDA<Boolean> filas, MatrizTDA<Boolean> cols, MatrizTDA<Boolean> cuadrante)
	{
		//INICIALIZAR MATRICES
		for (int i=0;i<filas.obtenerDimension();i++){
			for (int j=0;j<cuadrante.obtenerDimension();j++){
				filas.setearValor(i, j, false);
			}
		}	
		for (int i=0;i<cols.obtenerDimension();i++){
			for (int j=0;j<cuadrante.obtenerDimension();j++){
				cols.setearValor(i, j, false);
			}
		}	
		for (int i=0;i<cuadrante.obtenerDimension();i++){
			for (int j=0;j<cuadrante.obtenerDimension();j++){
				cuadrante.setearValor(i, j, false);
			}
		}
		// COMPLETAR MATRIZ CON VALORES PREDEFINIDOS
		for(int i = 0; i<tablero.obtenerDimension(); i++){
			for(int j=0; j<tablero.obtenerDimension(); j++){
				int aux = tablero.obtenerValor(i, j);
				Posicion pos = new Posicion();
				pos.x = i;
				pos.y = j;
				if(aux != 0){
					filas.setearValor(i, aux, true);
					cols.setearValor(j, aux, true);
					cuadrante.setearValor(calcularCuadrante(pos), aux, true);
				}else{
					filas.setearValor(i, aux, false);
					cols.setearValor(j, aux, false);
					cuadrante.setearValor(calcularCuadrante(pos), aux, false);
				}
			}
		}
		ResolverPoda(tablero, posActual, filas, cols, cuadrante);
		return tablero;
		}

	private static boolean ResolverPoda(MatrizTDA<Integer> tablero, Posicion posActual, MatrizTDA<Boolean> filas, MatrizTDA<Boolean> cols, MatrizTDA<Boolean> cuadrante) 
	{		
		if(posActual == null || posActual.x>tablero.obtenerDimension() || posActual.y>tablero.obtenerDimension())
		{				
			return true;
		}
		if(tablero.obtenerValor(posActual.x, posActual.y) != 0)
		{
			return ResolverPoda(tablero, proximaPosicion(tablero, posActual), filas, cols, cuadrante);
		}	
		
		int numCuadrante = calcularCuadrante(posActual);
		
		for (int i = 1; i<=tablero.obtenerDimension();i++)
		{
			//RECORREMOS FILAS
			if (filas.obtenerValor(posActual.x, i) == true){
				continue;
			}
			//RECORREMOS COLUMNAS
			if (cols.obtenerValor(posActual.y, i) == true){
				continue;
			}
			//RECORREMOS CUADRANTES
			if (cuadrante.obtenerValor(numCuadrante,i) == true){
				continue;
			}			
			tablero.setearValor(posActual.x, posActual.y, i);
			filas.setearValor(posActual.x, i, true);
			cols.setearValor(posActual.y, i, true);
			cuadrante.setearValor(numCuadrante, i, true);
			
			boolean resuelto = ResolverPoda(tablero, proximaPosicion(tablero, posActual), filas, cols, cuadrante);
			if(resuelto)
			{
				return true;
			} else {
				filas.setearValor(posActual.x, i, false);
				cols.setearValor(posActual.y, i, false);
				cuadrante.setearValor(numCuadrante, i, false);
				tablero.setearValor(posActual.x, posActual.y, 0);
			}
		}
	return false;
	}
	
	private static int calcularCuadrante(Posicion pos){
		int result = 0;
		if(pos.x <= 2 && pos.y <= 2){
			result = 0;
		}
		if(pos.y >= 3 && pos.y <= 5 && pos.x <= 2){
			result = 1;
		}
		if(pos.y >= 6 && pos.y <= 8 && pos.x <=2){
			result = 2;
		}
		if(pos.x >= 3 && pos.x <= 5 && pos.y <= 2){
			result = 3;
		}
		if(pos.y >= 3 && pos.y <= 5 && pos.x >= 3 && pos.x <=5){
			result = 4;
		}
		if(pos.y >= 6 && pos.y <= 8 && pos.x >= 3 && pos.x <=5){
			result = 5;
		}
		if(pos.x >= 6 && pos.x <= 8 && pos.y <= 2){
			result = 6;
		}
		if(pos.y >= 3 && pos.y <= 5 && pos.x >= 6 && pos.x <=8){
			result = 7;
		}		
		if(pos.y >= 6 && pos.y <= 8 && pos.x >= 6 && pos.x <=8){
			result = 8;
		}
		return result;
	}	
}